#pragma once
// LRU缓存策略：最近使用，使用过就放到队列前面；双向链表 + 哈希map映射
// 易错点：哈希表同时更新；默认析构default; make_shared(k,v)带参数；

#include <memory>
#include <unordered_map>
#include <iostream>
// 双向链表节点
template<typename T1, typename T2>
class DualLinkNode{
private:
    T1 key;
    T2 value;
public:
    // 双线链表智能指针，避免环形引用导致内存泄露，不能两个都为share；
    // 将pre改成weak：因为正向遍历通常更频繁，weak变为share的lock操作会更多。如果反向遍历更频繁，则next该weak
    shared_ptr<DualLinkNode> next;
    weak_ptr<DualLinkNode> pre;

    DualLinkNode(T1 k, T2 v);
    ~DualLinkNode();
    void setKey(T1 k);
    void setValue(T2 v);
    T1 getKey();
    T2 getValue();

    // void move_head(); 自己移动的话，效率太低了！

};
template<typename T1, typename T2>
DualLinkNode<T1,T2>::DualLinkNode(T1 k, T2 v){
    key = k;
    value = v;
    next = nullptr;
    // pre = nullptr; // 报错，weak_ptr不能直接赋值为nullptr
    pre = weak_ptr<DualLinkNode<T1,T2>>(); // 使用默认构造；或者通过shared_ptr直接转换
}
template<typename T1, typename T2>
DualLinkNode<T1,T2>::~DualLinkNode(){
    cout << "~~~~~~~~~ 对象析构：" << key << ':' << value << "~~~~~~~~~ " << endl;
}
template<typename T1, typename T2>
void DualLinkNode<T1,T2>::setKey(T1 k){
    key = k;
}
template<typename T1, typename T2>
void DualLinkNode<T1,T2>::setValue(T2 v){
    value = v;
}
template<typename T1, typename T2>
T1 DualLinkNode<T1,T2>::getKey(){
    return key;
}
template<typename T1, typename T2>
T2 DualLinkNode<T1,T2>::getValue(){
    return value;
}

// LRU缓存类
template<typename T1, typename T2>
class LRUCache{
private:
    int capacity;
    int length;
    shared_ptr<DualLinkNode<T1,T2>> pHead;
    shared_ptr<DualLinkNode<T1,T2>> pTail;
    unordered_map<T1, shared_ptr<DualLinkNode<T1,T2>>> mTable;
public:
    // 构造、析构
    LRUCache(int capacity);
    ~LRUCache() = default; // 析构：要么不写出来，用默认的；写了要么default，要么delete，要么类外实现。
    // 节点移动到头节点：引用传递指针、值传递指针，有区别吗？
    void move_head(shared_ptr<DualLinkNode<T1,T2>> curr);
    // 删除尾部节点
    void delete_tail();
    // 加入新节点到最前面
    void add_head(shared_ptr<DualLinkNode<T1,T2>> curr);

    // 取数，get；放数set
    bool get(T1 k, T2& v);
    T2 get(T1 k);
    void put(T1 k, T2 v);

    // 打印整个缓存的信息：容量、长度，键值
    void show_info();
};

template<typename T1, typename T2>
LRUCache<T1,T2>::LRUCache(int c){
    this->capacity = c;
    this->length = 0;
    this->pHead = nullptr;
    this->pTail = nullptr;
}

template<typename T1, typename T2>
void LRUCache<T1,T2>::move_head(shared_ptr<DualLinkNode<T1,T2>> curr){
    if(curr == pHead){
        return; // 已经在最前面，直接返回
    }
    // 不在最前面，在最后，先维护尾指针，再移动
    if(curr == pTail){
        pTail = pTail->pre.lock(); // weak 转 share，必须使用lock()函数
    }
    // 移到开头
    curr->pre.lock()->next = curr->next; // 调用next，weak必须先转换为 share
    if(curr->next != nullptr){
        curr->next->pre = curr->pre; // 加上判断，考虑尾部节点的情况; weak到weak，直接赋值
    }
    curr->next = pHead;
    pHead->pre = curr; // share 到 weak，直接隐式转换
    pHead = curr;
}

template<typename T1, typename T2>
void LRUCache<T1,T2>::add_head(shared_ptr<DualLinkNode<T1,T2>> curr){
    // 空链表
    if(pTail == nullptr){
        pHead = curr;
        pTail = curr;
        return;
    }
    // 单个节点、多个节点，一样加入
    curr->next = pHead;
    pHead->pre = curr;  // share转weak，直接赋值
    pHead = curr;
}

template<typename T1, typename T2>
void LRUCache<T1,T2>::delete_tail(){
    // 空链表，直接返回
    if(pTail == nullptr) return;

    mTable.erase(pTail->getKey()); // 易忘记：别忘记删掉哈希表中的
    // 单个节点，删除尾部
    if(pHead == pTail){
        pHead = nullptr;
        pTail = nullptr; // 智能指针，等于nullptr的瞬间，计数值为0，自动删除堆区内存
        return;
    }
    // 多个节点，删除尾部
    pTail->pre.lock()->next = nullptr; // 调用next， weak先转share
    pTail = pTail->pre.lock(); // 智能指针，尾部节点的计数变为0，自动删除; weak转share
}

template<typename T1, typename T2>
bool LRUCache<T1,T2>::get(T1 k, T2& value){
    // 没找到，返回false
    if(!mTable.count(k)){
        return false;
    }
    // 找到了，赋值，移到最前面
    value = mTable[k]->getValue();
    shared_ptr<DualLinkNode<T1,T2>> curr = mTable[k];
    move_head(curr);
    return true;
}

template<typename T1, typename T2>
T2 LRUCache<T1,T2>::get(T1 k){
    // 没找到，返回默认空值
    if(!mTable.count(k)){
        return T2{};
    }
    // 找到了，返回对应的值，移到最前面
    shared_ptr<DualLinkNode<T1,T2>> curr = mTable[k];
    move_head(curr);
    return curr->getValue();
}


template<typename T1, typename T2>
void LRUCache<T1,T2>::put(T1 k, T2 v){
    // 已存在，则更改值，并且移到最前面
    if(mTable.count(k)){
        mTable[k]->setValue(v);
        move_head(mTable[k]);
        return;
    }

    // 不存在，肯定得新建一个
    // 智能指针，explicit了有参构造：new 出来的裸指针只能走有参数构造，不能使用等号自动类型转换。
    // new缺点：两次操作，首先new出对象裸指针，再走智能指针的有参构造，分配控制块；内存不连续、可能中间异常中断，new成功了，但构造失败，内存泄露。
    // shared_ptr<DualLinkNode<T1,T2>> newNode(new DualLinkNode<T1,T2>(k,v)); 
    // 推荐使用make_shared()函数模版，直接返回智能指针，拷贝构造、等号赋值都可以
    // shared_ptr<DualLinkNode<T1,T2>> newNode = make_shared<DualLinkNode<T1,T2>>(k,v); // make_share()是函数模版，别忘了小括号,还需要传入构造参数
    shared_ptr<DualLinkNode<T1,T2>> newNode(make_shared<DualLinkNode<T1,T2>>(k,v));
    mTable[k] = newNode; // 别忘了加入哈希表
    // 不存在，则放到最前面；满了，就移除最后一个
    if(this->length == this->capacity){
        delete_tail();  // 移除最后一个
        this->length--;
    }
    add_head(newNode);
    this->length++;
}

template<typename T1, typename T2>
void LRUCache<T1,T2>::show_info(){
    std::cout << "capacity:" << this->capacity << ", length:" << this->length << std::endl;
    shared_ptr<DualLinkNode<T1,T2>> p = pHead;
    while(p != nullptr){
        std::cout << p->getKey() << ':' << p->getValue() << '/' << p.use_count() << " ";
        p = p->next;
    }
    std::cout << endl;
}